package com.gwcloud.leetcode.tags.backtrace;

/** 
* @ClassName   : Leetcode010 
* @author      : ganwei 
* @date        : 2020年5月7日 
* @Description : 10. 正则表达式匹配 
*/
public class Leetcode0010 {
    /**
     * -解题思路，回溯
     */
	public boolean isMatch(String s, String p) {
    	/**
    	 * 回溯出口ss
    	 */
		if(p.isEmpty()){
    		return s.isEmpty();
    	}
		
    	//回溯路径选择
    	boolean firstmatch = (!s.isEmpty() &&
    			( p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
    	
    	if(p.length() >= 2 && p.charAt(1)=='*'){
    		return isMatch(s,p.substring(2)) || (firstmatch && isMatch(s.substring(1),p));
    	}else{
    		return firstmatch&&isMatch(s.substring(1),p.substring(1));
    	}

    }
    
    /**
     * -解题思路，动态规划
     */
	public boolean isMatch_1(String s, String p){
		
		return false;
	}
	
	
    public static void main(String[] args) {
    	
    }
}
